1. Field of Invention
This invention relates generally to digital data communication systems, particularly to the encoding and decoding of error correcting codes.
2. Related Art and Other Considerations
In a digital data communication system (including storage and retrieval from optical or magnetic media) in order to increase the transfer rate of information and at the same time make the error rate arbitrarily low, it is necessary to employ an error control system. For fixed signal-to-noise ratios and fixed bandwidths improvements can be made through the use of error-correcting codes.
With error-correction coding the data to be transmitted or stored is mathematically processed through appropriate circuitry and/or software to obtain additional data symbols called check symbols or redundancy symbols. The data and check symbols together make up a codeword. After the codeword is transmitted to and received from the communication channel or retrieved from storage the codeword is mathematically processed to obtain error syndromes which contain information about locations and values of errors.
Some applications, e.g. the writing and reading of ID fields on magnetic disk, necessitate the use of codes which can quickly correct short bursts in a small block of data in real time.
For fast burst correction the related art generally employs one of two methods: 1) decoding a multiple-error correcting code (e.g. a Reed-Solomon code) using burst trapping; and 2) interleaving a single-error correcting code. The first method is described in Peterson's and Weldon's "Error-Correcting Codes", second edition, published by the MIT Press, p. 364 and the second method is described on page 357 of that text.
For applications wherein the codeword is transmitted or stored in serial format, e.g. magnetic disk, the byte correcting ability of the code causes an inefficiency. For example, if the code is based on 8-bit symbols, then a two byte correcting code employing burst trapping can guarantee to correct a 9-bit burst since a 10-bit burst could affect three bytes. If the code were based on 4-bit symbols and could correct a 4-symbol burst then all single 13-bit bursts could be corrected but the maximum length of the codeword would be reduced from 255 bytes to 7.5 bytes.
If the interleaving method is used such that a codeword capable of correcting a single 4-bit symbol is interleaved to degree four then all single 13-bit bursts could be corrected and the codeword length would be 30 bytes.
The disadvantage of the interleaving method is that whereas the burst trapping code in the first example has a minimum distance of nine, the individual codewords of the interleaving method in the second example each have minimum distance of three. This means that the first code can correctly detect as uncorrectable all random errors of two, three or four symbols but the second code can fail to detect such errors if they are contained entirely within one interleave. Also each additional redundancy symbol which is added to the first code increases the minimum distance by one but there is no way to add an additional redundancy symbol to the second code which will increase the minimum distance by one.